class Solution {
    /*
        思路1：维护每个位置左边的最大值和右边的最大值
    */
    public int trap(int[] height) {
        int len = height.length;

        // left[i] 表示0~i的最大值
        int[] left = new int[len];
        left[0] = height[0];
        for (int i = 1; i <= len - 1; i++) {
            left[i] = Math.max(height[i], left[i - 1]);
        }

        // right[i]表示[i]到len-1的最大值
        int[] right = new int[len];
        right[len - 1] = height[len - 1];
        for (int i = len - 2; i >= 0; i--) {
            right[i] = Math.max(height[i], right[i + 1]);
        }
        
        // 计算每个位置能接的雨水
        int ans = 0;
        for (int i = 0; i < len; i++) {
            ans += Math.min(left[i],right[i]) - height[i];
        }
        return ans;
    }
}

/**
     双指针解法
     
     * 结论1: 若height[left] < height[right] 必有 leftMax<rightMax
     * <p>
     * 结论2: 初始height[left] <= height[right], 然后left++ 直到height[left] > height[right]
     */
    public int trap(int[] height) {
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0;
        int ans = 0;
        while (left <= right) {
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);
            
            // 若h[left] < h[right] 必有 leftMax<rightMax
            if (height[left] <= height[right]) {
                ans += leftMax - height[left];
                // left 移动 直到h[left] > h[right]
                left++;
            } else {
                ans += rightMax - height[right];
                right--;
            }
        }
        return ans;
    }